/**
 * @autor my
 * 2017/8/17.
 */
public  class  Quicksort {
    private ComparePerson comparePerson=new ComparePerson();
    public  int onceTraversal(Person[]a, int left, int right) {
        //以数组第一个为基数，
        //left为最左边的索引，right为最右边的索引
        Person standard = a[left];// 以数组左边第一个元素为基数
        while (left < right) {
            //把a[left]看成一个坑位，从数组右边找一个比基数小的数，填到坑位
            while (comparePerson.comparebigger(standard,a[right])&&left<right) {
                right--;
            }
            if (left==right) {
                break;
            }
            //填坑,同时左边指针向右移动一格
            a[left] = a[right];
            left++;
            //这时把a[right]看成一个坑位，从数组左边边找一个比基数小的数，填到坑位
            while (comparePerson.comparebigger(standard,a[left])&&left<right) {
                left++;
            }
            if (left==right) {
                break;
            }
            //填坑,同时right向左移动一格
            a[right]=a[left];
            right--;
        }
        //把基数填到剩下的坑位
        a[left]=standard;
        return left;
    }
    public void quickSort(Person[] a, int left, int right) {
        //以middle为中间数把数组分成左右两部分，两边再分别排序，知道left=right
        if (left <right) {
            int middle = onceTraversal(a, left, right);
            quickSort(a, left, middle - 1);
            quickSort(a, middle + 1, right);
        }
    }
}
